import { QueueOverflowStrategy } from "./queue.enum";
import { cond, equals } from "ramda";
import { Queue } from "./queue";

/**
 * 一个简易的优先级队列
 */
export class PriorityQueue<T> implements Queue<T> {
  // 队列中的元素
  private __queue: T[] = [];

  /**
   * 构造函数
   * @param comparator 比较器
   * @param __maxSize 最大长度
   * @param __overflowStrategy 溢出策略
   */
  constructor(
    private comparator: (a: T, b: T) => number,
    private __maxSize = 0,
    private __overflowStrategy: QueueOverflowStrategy = QueueOverflowStrategy.DISCARD_NEW,
  ) {}

  /**
   * 入队
   * @param item
   */
  offer(item: T) {
    if (this.__overflowHandler()) {
      const index = this.__findIndex(item);
      this.__queue.splice(index, 0, item);
    }
  }

  /**
   * 溢出处理
   * 1. 丢弃尾部元素 QueueOverflowStrategy.DISCARD_TAIL
   * 2. 丢弃头部元素 QueueOverflowStrategy.DISCARD_HEAD
   * 3. 丢弃新元素 QueueOverflowStrategy.DISCARD_NEW
   * @private
   */
  private __overflowHandler(): boolean {
    if (this.__maxSize <= 0 || this.__queue.length < this.__maxSize) return true;
    if (this.__overflowStrategy === QueueOverflowStrategy.DISCARD_NEW) {
      return false;
    }
    cond([
      [equals(QueueOverflowStrategy.DISCARD_TAIL), () => this.__queue.pop()],
      [equals(QueueOverflowStrategy.DISCARD_HEAD), () => this.__queue.shift()],
    ])(this.__overflowStrategy);
    return true;
  }

  /**
   * 出队
   */
  poll(): T {
    return this.__queue.shift()!;
  }

  /**
   * 获取栈顶元素
   */
  peek() {
    return this.__queue[0];
  }

  /**
   * 获取队列长度
   */
  size() {
    return this.__queue.length;
  }

  /**
   * 判断队列是否为空
   */
  isEmpty() {
    return this.__queue.length === 0;
  }

  /**
   * 清空队列
   */
  clear() {
    this.__queue = [];
  }

  /**
   * 获取插入位置
   * @param item
   * @private
   */
  private __findIndex(item: T) {
    let left = 0,
      right = this.__queue.length - 1,
      ans = -1;
    let queue = this.__queue;
    while (left <= right) {
      const mid = (left + right) >> 1;
      if (this.comparator(queue[mid], item) <= 0) {
        ans = mid;
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    return ans + 1;
  }
}
